
/**快速排序。会修改原数组。
 * @param array 待排序数组
 * @param start 排序起始位置。默认0
 * @param end 排序终止位置，默认array.length - 1
 * @returns 返回排序后的原数组
 * @description
 * - 空间复杂度  logn
 * - 时间复杂度：平均O(nlogn)
 *   - 最好 O(nlogn)    （每次划分都能将待排序序列均匀地分割成两个近似相等的部分，递归树的深度是logn，每层划分需要O(n)）
 *   - 最差 O(n^2)    （递归树深度是n，每层划分需要O(n)）
 */
export const quickSort_change = (array: number[], start: number = 0, end: number = array.length - 1) => {
    if (start >= end) return
    let left = start, right = end
    const key = array[left]//基准元素
    while (left < right) {
        while (left < right && array[right] >= key) right-- //不断移动右指针，直到找到某个arr[j] < key的，把它放到左指针那 
        array[left] = array[right]
        while (left < right && array[left] <= key) left++//不断移动左指针，直到找到某个arr[i] > key的，把它放到右指针那 
        array[right] = array[left]
    }
    array[left] = key//这时候left就会来到key适合的位置，直接赋值
    quickSort_change(array, start, left - 1)//递归i左侧的部分
    quickSort_change(array, left + 1, end)//递归i右侧的部分
    return array
}
/**快速排序。不修改原数组。 使用了额外的数组空间，空间复杂度更大
 * 最好 O(nlogn) ，最坏 O(n^2)
 * @param array 待排序数组
 * @returns 排序后的数组
 */
export const quickSort_noChange = (array: number[]): number[] => {
    if (array.length <= 1) return array
    const key = array[0] //基准元素
    const left: number[] = []
    const right: number[] = []
    for (let i = 1; i < array.length; i++) {
        const element = array[i]
        if (element > key) { // 比基准大的元素放入右边数组
            right.push(element)
        } else {// 比基准小的元素放入左边数组
            left.push(element)
        }
    }
    return quickSort_noChange(left).concat(key, quickSort_noChange(right)) //拼接， 左， 基准， 右
}
/**归并排序 */
export const mergeSort = (arr: number[]) => {
    /**按顺序合并left和right数组 */
    const merge = (left: number[], right: number[]) => {
        const res: number[] = []
        while (left.length && right.length) {
            //不断地取出第一个元素 （有序数组的合并）
            if (left[0] > right[0]) {
                res.push(right.shift()!)
            } else {
                res.push(left.shift()!)
            }
        }
        //上面结束后，可能还有数组长度不为0，就需要清空
        while (left.length) res.push(left.shift()!);
        while (right.length) res.push(right.shift()!);
        return res
    }
    const _mergeSort = (array: number[]): number[] => {
        if (array.length < 2) return array
        //把数组分成左右两份
        const middle = array.length >> 1
        const left = array.slice(0, middle)
        const right = array.slice(middle)
        //进行递归，递归顺序：先全部分为两半，直到变成单个数组，再一个个合并
        return merge(_mergeSort(left), _mergeSort(right))
    }
    return _mergeSort(arr)
}

/**基数排序，按位排序
 * - O(kn) 其中k是数字位数
 */
export const radixSort = (arr: number[]) => {
    //定义一个二维数组，表示10个桶，每个桶就是一个一维数组
    //说明
    //1. 二维数组包含10个一维数组，
    //2. 为了防止在放入数的时候，数据溢出，则每个一维数组（桶）大小定为arr.length
    //3. 很明确，基数排序是使用空间换时间的经典算法
    const bucket = new Array<number[]>(10);
    for (let i = 0; i < bucket.length; i++) {
        bucket[i] = new Array(arr.length);
    }

    //为了记录每个桶中，实际存了多少个数据，我们定义一个
    //一维数组来记录每个桶的每次放入的数据个数
    //可以这里理解
    //比如：bucketElementCounts[0],记录的就是bucket[0]桶的放入数据个数
    const buckeElementCounts = new Array<number>(10).fill(0);

    //1.得到数组中最大的位数
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i]
        }
    }
    //得到最大是几位数  
    for (let i = 0, n = 1; i < String(max).length; i++, n = n * 10) {
        //每一轮，对每个元素的各个位数进行排序处理,
        //第一次是个位，第二次是十位，第三次是百位
        for (let j = 0; j < arr.length; j++) {
            //取出每个元素的各位的值
            let digitOfElement = Math.floor(arr[j] / n) % 10;
            bucket[digitOfElement][buckeElementCounts[digitOfElement]]
                = arr[j];
            buckeElementCounts[digitOfElement]++;
        }
        //按照这个桶的顺序（以为数组的下标依次取出数据，放入原来数组）
        let index = 0;
        //遍历每一桶，并将桶中的数据，放入原数组
        for (let k = 0; k < buckeElementCounts.length; k++) {
            //如果桶中有数据，我们才放入原数组
            if (buckeElementCounts[k] !== 0) {
                //循环该桶即第k个桶，即第k个一维数组，放入
                for (let l = 0; l < buckeElementCounts[k]; l++) {
                    //取出元素放入arr
                    arr[index] = bucket[k][l];
                    //arr下标后移
                    index++;
                }
                //每轮处理后，下标要清0
                buckeElementCounts[k] = 0;
            }
        }
    }
}